#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    int minimumOpe(vector<int>& nums){
        int n=nums.size(); unordered_set<int> st;
        for(int i=n-1;i>=0;i--){
            if(st.count(nums[i])) return (i+1+2)/3;
            st.insert(nums[i]);
        }
        return 0;
    }
};

class Solution2{
public:
    int maxDistinctElements(vector<int>& nums, int k){
        vector<pair<int,int>> vec;
        for(int x:nums) vec.push_back({x-k,x+k});
        sort(vec.begin(), vec.end());
        int ans=0, R=-2e9;
        for(auto p: vec){
            if(R<=p.second) ans++, R=max(R,p.first)+1;
        }
        return ans;
    }
};

class Solution3{
public:
    int minLength(string s,int numOps){
        int n=s.size();
        auto gao=[&](int x){
            int cnt=0;
            for(int i=0;i<n;i++) if(s[i]%2!=(i+x)%2)cnt++;
            return cnt<=numOps;
        };
        if(gao(0)||gao(1)) return 1;
        auto check=[&](int lim){
            int cnt=0;
            for(int i=0,j=0;i<n;i++)
                if(i==n-1||s[i]!=s[i+1]) {
                    int len = i - j + 1;
                    cnt += len / (lim + 1);
                    j = i + 1;
                }
            return cnt<=numOps;
        };
        int head=2, tail=n;
        while(head<tail){
            int mid=(head+tail)>>1;
            if(check(mid)) tail=mid;
            else head=mid+1;
        }
        return head;
    }
};

class Solution4 {
public:
    int minLength(string s, int numOps) {
        int n = s.length();
        auto check = [&](int m) -> bool {
            int cnt = 0;
            if (m == 1) {
                // 改成 0101...
                for (int i = 0; i < n; i++) {
                    // 如果 s[i] 和 i 的奇偶性不同，cnt 加一
                    cnt += (s[i] ^ i) & 1;
                }
                // n-cnt 表示改成 1010...
                cnt = min(cnt, n - cnt);
            } else {
                int k = 0;
                for (int i = 0; i < n; i++) {
                    k++;
                    // 到达连续相同子串的末尾
                    if (i == n - 1 || s[i] != s[i + 1]) {
                        cnt += k / (m + 1);
                        k = 0;
                    }
                }
            }
            return cnt <= numOps;
        };
        int left = 0, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};


int main(){
    vector<int> nums1={1,2,3,4,2,3,3,5,7};
    Solution s; cout<<s.minimumOpe(nums1)<<endl;

    vector<int> nums2={1,2,2,3,3,4};
    Solution2 s2; cout<<s2.maxDistinctElements(nums2, 2)<<endl;

    Solution3 s3; cout<<s3.minLength("000001",1)<<endl;

    Solution4 s4; cout<<s4.minLength("000001",1)<<endl;
}

